{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Merge Sort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "def merge_sort(array):\n",
    "    if len(array) < 2:\n",
    "        return array\n",
    "    \n",
    "    mid = len(array) // 2\n",
    "    left = merge_sort(array[:mid])\n",
    "    right = merge_sort(array[mid:])\n",
    "    \n",
    "    return merge(left, right)\n",
    "\n",
    "def merge(left, right):\n",
    "    result = []\n",
    "    i, j = 0, 0\n",
    "    while i < len(left) or j < len(right):\n",
    "        if left[i] <= right[j]:\n",
    "            result.append(left[i])\n",
    "            i += 1\n",
    "        else:\n",
    "            result.append(right[j])\n",
    "            j += 1\n",
    "        if i == len(left) or j == len(right):\n",
    "            result.extend(left[i:] or right[j:])\n",
    "            break\n",
    "    \n",
    "    return result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "### Time Complexity:\n",
    "\n",
    "- Best Case: O(n log2(n))\n",
    "- Average Case: O(n log2(n))\n",
    "- Worst Case:  O(n log2(n))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Why O(n log n) ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If you are given two sorted arrays(say A & B) of length n/2 then it will take O(n) time to merge and make a sorted array of length n.\n",
    "\n",
    "But if A and B are not sorted then we need to sort them first. For this we first divide array A and B of length n/2 each into two arrays of length n/4 and suppose these two arrays are already sorted.\n",
    "\n",
    "Now to merge two sorted array of length n/4 to make array A of length n/2 will take O(n/2) time and similarly array B formation will also take O(n/2) time.\n",
    "\n",
    "So total time to make array A and B both also took O(n). So at every stage it is taking O(n) time. So the total time for merge sort will be O(no. of stages * n).\n",
    "\n",
    "Here we are dividing array into two parts at every stage and we will continue dividing untill length of two divided array is one.\n",
    "\n",
    "So if length of array is eight then we need to divide it three times to get arrays of length one like this\n",
    "\n",
    "8 = 4+4 = 2+2+2+2 = 1+1+1+1+1+1+1+1\n",
    "\n",
    "So\n",
    "\n",
    "no. of stages = log2(8) = 3\n",
    "\n",
    "That is why merge sort is O(nlog(n)) with log2(n) iteration.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Code for executing and seeing the difference in time complexities"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Best Case Performance:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]\n",
      "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]\n"
     ]
    }
   ],
   "source": [
    "# elements are already sorted\n",
    "array = [i for i in range(1, 20)]\n",
    "\n",
    "print(array)\n",
    "# 20 ALREADY sorted elements need 18 iterations approx = n\n",
    "print(merge_sort(array))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Average Case Performance:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[5, 2, 17, 15, 3, 13, 9, 12, 7, 19, 11, 18, 14, 10, 1, 16, 4, 8, 6]\n",
      "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "# elements are randomly shuffled\n",
    "array = [i for i in range(1, 20)]\n",
    "random.shuffle(array)\n",
    "print(array)\n",
    "# 20 shuffled elements need 324 iterations approx = n * n\n",
    "print(merge_sort(array))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Worst Case Performance:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]\n",
      "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]\n"
     ]
    }
   ],
   "source": [
    "# elements are reverse sorted\n",
    "array = [i for i in range(1, 20)]\n",
    "# reversing the array\n",
    "array = array[::-1]\n",
    "\n",
    "print(array)\n",
    "# 20 REVERSE sorted elements need 324 iterations approx = n * n\n",
    "print(merge_sort(array))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
